package palindrome;

import java.util.Scanner;

public class CreatePalidrome {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		String string = "";
		while(scanner.hasNext()){
			string = scanner.nextLine();
			delChar(string);
		}
		scanner.close();
	}
	
	//删除最少的字符变为回文串
	//思路感觉是动态规划，先试一试
	//思路错了，dp的边界条件又要通过子问题来确定
	public static void delChar(String string){
		int length = string.length();
		char[] word = string.toCharArray();
		int[][] result = new int[length / 2][length / 2];
		result[result.length - 1][0] = word[result.length - 1] == word[length - result[0].length] ? 0 : 1;
		for (int j = 0; j <= result[0].length; j++) {
			if(word[result.length] == word[j]){
//				result[result.length - 1][j] ;
			}
		}
		for (int i = result.length - 1; i >= 0; i--) {
			for (int j = 0; j < result[0].length; j++) {
				if(word[i] == word[result.length + j]){
					result[i][j] = result[i + 1][j - 1];
				}else {
					result[i][j] = Math.min(result[i + 1][j], result[i][j - 1]) + 1;
				}
			}
		}	
	}
	
	//这道题可以转换为求正序字符串和逆序字符串的最长公共子序列
	//最长公共子序列就是最后去掉最少字符之后的回文串
	public static void delChar2(String string){
		int length = string.length();
		if(string == null || string.length() <= 0){
			return;
		}
//		char[] word = string.toCharArray();
//		char[] inverseWord = new char[word.length];
//		int count = 0;
//		for (int i = word.length - 1; i >= 0; i--) {
//			inverseWord[count++] = word[i];
//		}
//		String inverseString2 = String.copyValueOf(inverseWord);
		String inverseString = new StringBuffer(string).reverse().toString();
		int common = longest(string, inverseString);
		System.out.println(length - common);
	}
	
	
	//求最长公共子序列
	public static int longest(String S, String T){
		if (S == null || T == null) {
			return -1;
		}
		if(S.length() <= 0  || T.length() <= 0 ){
			return 0;
		}
		int[][] result = new int[S.length() + 1][T.length() + 1];
		for (int i = 1; i < result.length; i++) {
			for (int j = 1; j < result[0].length; j++) {
				if(S.charAt(i - 1) == T.charAt(j - 1)){
					result[i][j] = result[i- 1][j - 1] + 1;
				}else {
					result[i][j] = Math.max(result[i- 1][j], result[i][j - 1]);
				}
			}
		}
		return result[S.length()][T.length()];
	}
}
